\section{Ejercicio 3}
\subsection{Introducci'on}
\setlength{\parindent}{2em}
Dado un conjunto de personas, el ejercicio pide encontrar 2 grupos de tres personas cada uno:\\
\begin{itemize}
 \item Coppersmith(para nosotros David ): las personas se conocen entre si.
 \item Winograd(para nosotros Jacobo): las personas no se conocen entre si.
\end{itemize}
Se conoce de antemano si 2 personas son amigos o no.\\
Para resolver este problema decidimos modelrlo con grafos, en donde:
\begin{itemize}
 \item Aristas: relaci'on de amistad entre las personas.
 \item Nodos: personas, numeradas de 1 hasta n para diferenciarlas.
\end{itemize}
Luego de modelarlo asi, el problema se reduce a buscar un \textbf{$K_3$} en el grafo y su complemento, aquel que cumple que es el menor lexicogr'aficamente respecto de los restantes grupos.\\
La complejidad esperada para determinar ambos grupos es estrictamente menor que \textbf{$n^3$}.\\
HACER DIBUJITOS!

  
\subsection{Soluci'on}
Un algoritmo trivial buscar'ia grupos de tres personas analizando todas las posiblidades, es decir, $\binom{n}{3}$, con n = cantiadad de nodos del grafo circular, con una complejidad acotada por O($n^3$)( $\frac{n(n-1)(n-2)(n-3)!}{3!(n-3)!}$ =  $\frac{n(n-1)(n-2)}{3!}$ $\leq$ $n^3$).\\
El algoritmo que se nos ocurri'o en un principio fue DFS para recorrer el grafo y por cada nodo chequear en los vecinos de los vecinos para saber si ese nodo con algun vecino forma un $K_3$. Para este algoritmo la complejidad obtenida fue O(n x (n+m)), que no satisface $<$ O($n^3$) en el caso de que el grafo este completo.\\
Finalmente decidimos usar el teorema visto en clase referente a la multiplicaci'on de la matriz de adyacencia del grafo. El teorema dice lo siguiente:\\
\textbf{Teorema}\\
Si \textbf{A} es la matriz de adyacencia del grafo \textbf{G}, el elemento $a_{ij}^k$ de $A^k$ es igual a la cantidad de caminos de longitud $K$ entre i y j.\\
En nuestro caso nos interesan los elementos de la diagonal ($a_{ii}$) de $A^3$ ya que representan la cantidad de caminos de longitud 3 que parten y regresan a ese elemento. De este planteo surgen 3 complicaciones:
\begin{itemize}
	\item La complejidad es O($n^3$), no satisface aun los requerimientos de la c'atedra.
	\item Como obtener los menores(lexicogr'aficamente) grupos.
	\item Como obtener el grupo de David y el grupo de Jacobo.
\end{itemize}
Para asegurar la complejidad del algoritmo $<$ O($n^3$) usamos el algoritmo de Strassen cuya complejidad para la multiplicaci'on de matrices es O($n^\log_2 7$). Ver \textsl{http://en.wikipedia.org/wiki/Strassen\_algorithm}\\
Para obtener los grupos menores simplemente recorremos la diagonal de la matriz resultante(\textit{$A^3$}), de menor a mayor(orden lexicogr'afico), y nos quedamos con el primer elemento distinto de 0, porque dicho elemento contiene al menos 1 camino de longitud 3 hacia s'i mismo(por el teorema enunciado). Luego recorremos cada uno de sus vecinos y por cada uno de estos sus vecinos para determinar un $K_3$.\\
Para obtener los 2 grupos decidimos usar un 'unico algoritmo que recorre primero el grafo y luego su complemento:
\begin{itemize}
	\item Recorrido del grafo para buscar el grupo David.
	\item Recorrido del complemento para buscar el grupo Jacobo.
\end{itemize}
Para el grupo de David las \textit{personas}(nodos) \textit{se conocen entre s'i}(estan relacionados), por lo que el conjunto de nodos y las relaciones no deber'ia ser otro que el original, le'ido de archivo. Para el caso del grupo Jacobo es diferente, porque los nodos no deben estar relacionados entre s'i, por esto, el complemento nos da la facilidad de generar un grafo en el que los nodos que est'an relacionados entre s'i formando un $K_3$ no lo est'an en el grafo original, cumpliendo con la premisa del grupo de Jacobo, no existe relaci'on entre estos 3 nodos.\\

\subsection{Pseudoc'odigo}

\newcommand{\jacoboYDavid}{\ensuremath{\mbox{\sc jacoboYDavid}}}
	\begin{algorithm}[H]
		\caption{$\jacoboYDavid()$}\label{alg:jacoboYDavid}
			\medskip
			\begin{algorithmic}[1]
			\STATE matrizCompletada $\leftarrow$ completarMatriz(matrizAdyacencia) 
			\STATE Strasen(matrizCompletada)
			\STATE int minNodoDavidYJacobo $\leftarrow$ getMinNodoParaTriangulo(matrizCompletada)		
			\STATE int[ ] vecinosDeDavidOJacobo $\leftarrow$ matrizVecinos[minNodoDavidYJacobo]
			\STATE int[ ] amigosDavidYJacobo
			\FOR {(i : vecinosDeDavidOJacobo)} 
				\STATE Int[ ] vecinosDeVecinosDeDavidOJacobo $\leftarrow$ vecinosDe(i)
 				\FOR{(j : vecinosDeVecinosDeDavidOJacobo)} 
					\STATE ordenarLexicograficamente(amigosDavidYJacobo,i,j)
				\ENDFOR
			\ENDFOR	
			\STATE devolver amigosDavidYJacobo
			\end{algorithmic}
	\end{algorithm}
	

\subsection{Explicaci\'on}
 
\subsection{Complejidad}
Sea $n$ la cantidad de nodos del grafo:\\
Antes de analizar la fuci'on principal, hay que saber que usamos cuatro matrices: la matriz de adyacencia y su complemento y la matriz de vecinos(que nos pasan como entrada) y su complemento. Construir cada matriz tiene una complejidad de O($(n^2)$). Hacemos esto ya que nos facilita obtener los amigos de alg'un nodo y saber si dos nodos son adyecentes, en O($1$).\\  
Pasemos a analizar la complejidad de jacoboYDavid:\\
Lo primero que hace la funci'on es agrandar la matriz de adyacencia hasta la potencia de dos m'as cercana a $n$. Esto lo hacemos para poder utilizar Strassen. La complejidad de esta operaci'on es de O($n^2$) porque copia la matriz de adyacencia en esta nueva matriz m'as grande.\\
Luego aplica Straseen dos veces para obtener una matriz de grado 3. El costo de aplicar Strassen es de $n^{2,81}$. Entonces aplicarla dos veces tiene una complejidad de O($2 * n^{2,81}$).\\
Ahora encuentra el menor nodo para armar el tri'angulo que buscamos. Esta funci'on recorre la diagonal de la matriz de grado 3 buscando alguna posici'on que contenga un entero $> 0$. En peor caso va a recorrer toda la diagonal, por lo tanto la complejidad de buscar el menor nodo para el triangulo es O($n + u$), con $u$ lo que le faltaba a la matriz de adyacencia para completar hasta la potencia de $n$ m'as cercana. Como $u < n$, entonces podemos acotar la complejidad de buscar el menor nodo por O($2 * n$).\\ 
Si se encuentra alg'un nodo pertenciente a un circuito de grado 3, o sea un elementos de la diagonal de la matriz no nulo y positivo, llamemoslo $v$, se empieza a recorrer los vecinos de $v$ y los vecinos de los vecinos de $v$ con el fin de hallar el mencionado circuito. Esto lo hace mediante dos ciclos de repetici'on de 1 hasta la $\# amigos(v)$. En peor caso un nodo puede tener $n$ amigos entonces podemos acotar esto por O($n^2$).\\
Adem'as llamamos a la funci'on jacoboYDavid 2 veces, la primera vez para encontrar encontrar el grupo Copersmith, y la otra usando el  complemento de las matrices para encontrar el grupo Winograd.\\
Consideranto todo esto, la complejidad total es la siguiente:\\  
O($4 * n^2$) + O($2 * (n^2 + 2 * n^{2,81} + 2 * n + n^2)$) = O($4 * n^2$) + O($4 * n^{2,81} + 4 * n^2 + 4 * n$) $\in$ O($n^{2,81}$)
\subsection{Gr\'aficos}
Esta secci'on tiene como objetivo analizar emp'iricamente la complejidad del algoritmo propuesto. No tiene sentido analizar un peor caso ya que la complejidad te'orica est'a acotada por la del algoritmo de Strassen que se realiza en todos los casos. Tiene m'as sentido analizar la entrada, si la cantidad de nodos es potencia de 2, si son grafos completos o no, la densidad de los grafos, etc.
\newpage

\begin{figure}[h]
	\centering
		\includegraphics[width=0.8\textwidth]{graficos/ej3/operacioneshasta200aleatorios.png}
\end{figure}

\begin{itemize}
	\item M'aximo de 200 nodos
	\item Densidad de aristas del 50\%
	\item Relaciones aleatorias
\end{itemize}
En este caso se puede ver como la complejidad calculada est'a acotada siempre por:
\begin{itemize}
	\item Superiormente O(10 x $n^{2,81}$)
	\item Inferiormente O($n^{2,81}$)
\end{itemize}
La forma escalonada se debe al cambio de potencia de 2. El algoritmo busca la potencia de 2 mas cercana para completar la matriz por lo que hasta que no se supera la potencia de 2 mas cercana la complejidad se mantiene uniforme. La recta diagonal que une los escalones se debe a la interpolaci'on por la variaci'on en la cantidad de nodos para cada caso, en este ejemplo 19, es decir, entre cada caso de prueba hay 19 nodos de diferencia.
\newpage
\begin{figure}[h]
	\centering
		\includegraphics[width=0.8\textwidth]{graficos/ej3/operacioneshasta512potDe2Aletaorios.png}
\end{figure}

\begin{itemize}
	\item M'aximo de 512 nodos, solo potencias de 2
	\item Densidad de aristas del 50\%
	\item Relaciones aleatorias
\end{itemize}
En este caso se puede ver como la complejidad calculada est'a acotada superiormente O(10 x $n^{2,81}$).
La forma escalonada ya no est'a presente en este gr'afico, porque los casos son potencias de 2.
\newpage
\begin{figure}[h]
	\centering
		\includegraphics[width=0.8\textwidth]{graficos/ej3/operacioneshasta512potDe2AletaoriosCompAlgo.png}
\end{figure}

\begin{itemize}
	\item M'aximo de 512 nodos, solo potencias de 2
	\item Densidad de aristas del 50\%
	\item Relaciones aleatorias
\end{itemize}
En este caso se puede ver como la complejidad calculada est'a acotada superiormente por la complejidad del algoritmo trivial(O($n^3$)). A partir de los 100 nodos la diferencia es notable. La escala logar'itmica en el eje y permite ver la difencia "y" el crecimiento de la funci'on con mayor claridad.
\newpage
\subsection{Conclusi\'on}
\begin{itemize}
 \item Fue escencial usar multiplicaci'on de matrices para determinar la cantidad de caminos entre los pares de nodos del grafo.
 \item El usar la multiplicaci'on de matrices mediante el algoritmo de Strassen con una complejidad  O($n^{2,81}$) nos permite lograr la complejidad requerida del algoritmo.
 \item El algoritmo encuentra la soluci'on de manera m'as eficiente que usando fuerza bruta que ser'ia chequear todas las combinaciones de 3 nodos.
\end{itemize}
